CF39A C*++ Calculations

题意简述

给你一个含变量$x$的式子，所有$x$的系数为常数，定义模糊的部分按任意次序计算。如:$a+++++a$既可以先算 $a++$ , 也可以先算$++a$。

给你$a$的初值，求算式的最大值。

样例：为了方便描述，用括号隔开

$a = 1~~~~~~~~~~~~~~~~ (5*a++)-(3*++a)+(a++)$

计算顺序为：$2,3,1$

答案为：$(5*3)-(3*2)+(2) = 11$

进入正题

这道题可以贪心解决，我们不难想到，系数越小，我们越先算（减法系数取负）。
下面给出证明：

结论1：当系数相同时，$a++$与$++a$的顺序对答案无影响。

证明：若原式有这样一个部分：$( k*a++)~+~ (k * ++a)$

先算前部分：$k*a+k*(a+2)$

先算后部分：$k*(a+1)+k*(a+1)$

结果是相等的，同时，$a$改变后的值也相等，证毕。

结论2：当系数不同时，系数小的先算

证明：考虑4个式子：（$p~\not=~q$）

$(p*++a)+(q*a++)$

$(p*++a)+(q*++a)$

$(p*a++)+(q*a++)$

$(p*a++)+(q*++a)$

先讨论第一个式子，其余同理。

先算左式：$p*(a+1)+q*(a+1)$

先算右式：$p*(a+2)+q*a$

两式作差：$q-p$

当$q>p$，$q-p>0$，即先算左式更优，刚好是小系数。

$q<p$同理。

知道贪心策略后，代码实现不难，模拟求出系数与式子是$++a$还是$a++$。
最后排序算出答案。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define int long long

int a,len;
int k , f;
struct node{
	int a_i , fr;
	operator < ( const node &x ) {
		return a_i < x.a_i;
	}
}c[ 100005 ];
char s[ 1000005 ];
signed main( ) {
    scanf("%lld\n",&a);scanf("%s",s);
    int len = strlen( s );
    for( int i = 0 ; i < len ; i ++ ) {
        f = 1;
        if( s[ i ] == '-' ) f = -1 , i ++;
        if( s[ i ] == '+' && ( s[ i + 1 ] != '+' || ( s[ i + 1 ] == '+' && s[ i + 2 ] == '+' ) ) ) i ++;
        if( '0' <= s[ i ] && s[ i ] <= '9' ) {
            k ++;
            while( '0' <= s[ i ] && s[ i ] <= '9' ) {
                c[ k ].a_i = c[ k ].a_i * 10 + s[ i ] - '0';
                i ++;
            }
            i ++; c[ k ].a_i *= f;
            if( s[ i ] == '+' ) c[ k ].fr = 1;
            i += 2;
        }
        else if( s[ i ] == '+' ) {
            c[ ++ k ].a_i = f;
            c[ k ].fr = 1;
            i += 2;
        }
        else if( s[ i ] == 'a' ) {
            c[ ++ k ].a_i = f;
            i += 2;
        }
    }
    /*for( int i = 1 ; i <= k ; i ++ )
    	printf("%lld %lld\n",c[ i ].a_i,c[ i ].fr);*/
    sort( c + 1 , c + k + 1 );
    int Ans = 0;
    for( int i = 1 ; i <= k ; i ++ ) {
        Ans = Ans + c[ i ].a_i * ( c[ i ].fr ? a + 1 : a );
        a ++;
    }
    printf("%lld",Ans);
    return 0;
}